package algorithm.sort;


import algorithm.sort.common.SortTestHelper;

import java.util.Arrays;


/**归并排序
 * @author bingo
 * @create 2018-02-23 10:22
 **/
public class MergeSort {

    public void   mergeSort(Comparable[] arr){

        int n = arr.length;
        System.out.println("n="+n);
        _mergeSort(arr,0,n-1);

    }

    private void _mergeSort(Comparable[] arr, int l, int r) {
        if(l>=r){
            return;
        }
        int middle = (l+r)/2;

        _mergeSort(arr,l,middle);
        _mergeSort(arr,middle+1,r);
        _merge(arr,l,middle,r);
    }

    private void _merge(Comparable[] arr, int l, int middle, int r) {
        Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
        int i=l,j=middle+1;
        for(int k=l;k<=r;k++){

            if(i>middle){
                arr[k]=aux[j-l];
                j++;
            }
            else if(j>r){
                arr[k]=aux[i-l];
                i++;
            }
            else if(aux[i-l].compareTo(aux[j-l])<0){
                arr[k]=aux[i-l];
                i++;
            }
            else if(aux[i-l].compareTo(aux[j-l])>0){
                arr[k]=aux[j-l];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] arr = SortTestHelper.generateRandomArray(100,0,10000);
        MergeSort mergeSort  = new MergeSort();
        mergeSort.mergeSort(arr);
        System.out.println(SortTestHelper.isSorted(arr));
    }


}
